package MyGraph;

import Queue.LinkQueue;

public class Test {
    // 例题 6.2
    // 利用广度优先算法确定无向图的连通分量

    public final static int INFINITY = Integer.MAX_VALUE;

    // 连通分量就是最大子连通图
    public static void CC_BFS(IGraph g)throws Exception{
        // 访问标识数组
        boolean[] visited = new boolean[g.getVNum()];
        // 将所有顶点的初始访问状态变为 false
        for(int v=0; v<g.getVNum(); v++){
            visited[v]=false;
        }

        // 辅助队列q 来进行广度优先
        LinkQueue q = new LinkQueue();
        // 辅助队列p 记录连通结点的订点
        LinkQueue p = new LinkQueue();
        // 用来标记连通分量个数
        int i = 0;
        for(int v=0; v<g.getVNum(); v++){
            // 清空队列  每一次遍历都是寻找最大子连通量
            p.clear();
            if(!visited[v]){
                visited[v] = true;
                // 获得当前下标的结点值
                p.offer(g.getVex(v));
                // 存入结点
                q.offer(v);
                while(!q.isEmpty()){
                    int u = (Integer) q.poll();
                    for(int w=g.firstAdj(u); w>=0; w=g.nextAdj(u, w)){
                        if(!visited[w]){
                            visited[w]=true;
                            p.offer(g.getVex(w));
                            q.offer(w);
                        }
                    }
                }
                i++;
                System.out.println("图的第"+ i +"个连通分量为: ");
                while(!p.isEmpty()){
                    System.out.println(p.poll().toString());
                }
                System.out.println();
            }
        }
    }


    public static void main(String[] args) throws Exception {
        Object v[] = {"a", "b", "c", "d", "e", "f", "g"};
        int[][] e={
                {0, 1, INFINITY, 1, INFINITY, INFINITY, INFINITY},
                {1, 0, 1, INFINITY, INFINITY, INFINITY, INFINITY},
                {INFINITY, 1, 0, 1, INFINITY, INFINITY, INFINITY},
                {1, INFINITY, 1, 0, INFINITY, INFINITY, INFINITY},
                {INFINITY, INFINITY, INFINITY, INFINITY, 0, 1, INFINITY},
                {INFINITY, INFINITY, INFINITY, INFINITY, 1, 0, 1},
                {INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 1, 0}
        };

        MGraph g = new MGraph(MGraph.graphKind.UDG, 7, 6, v, e);
        CC_BFS(g);
    }


}
